import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.Collection;
import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

import org.junit.Test;


public class MSTTests {

	@Test(timeout = 500)

	public void mst1() {
		Collection<Edge> mst = MST.kruskals(g1());
		assertEquals(g1a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void mst2() {
		Collection<Edge> mst = MST.kruskals(g2());
		assertEquals(g2a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void mst3() {
		Collection<Edge> mst = MST.kruskals(g3());
		assertEquals(g3a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void mst4() {
		Collection<Edge> mst = MST.kruskals(g4());
		assertEquals(g4a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void mst5() {
		Collection<Edge> mst = MST.kruskals(g5());
		assertEquals(g5a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void mst6() {
		Collection<Edge> mst = MST.kruskals(g6());
		assertEquals(3, mst.size());
		int weight = 0;
		for (Edge e : mst) {
			weight += e.getWeight();
		}
		assertEquals(3, weight);
	}
	
	@Test
	public void prim1() {
		Collection<Edge> prim = MST.prims(g1(),1);
		assertEquals(g1a(), edges(prim));
	}
	
	@Test

	public void prim2() {
		Collection<Edge> prim = MST.prims(g2(),1);
		assertEquals(g2aa(), edges(prim));
	}
	
	@Test

	public void prim3() {
		Collection<Edge> prim = MST.prims(g3(),1);
		assertEquals(g3a(), edges(prim));
	}
	
	@Test
	public void prim4() {
		Collection<Edge> mst = MST.prims(g4(),1);
		assertEquals(g4a(), edges(mst));
	}
	
	@Test(timeout = 500)

	public void prim5() {
		Collection<Edge> mst = MST.prims(g5(),1);
		assertEquals(g5a(), edges(mst));
	}
	@Test
	public void prim6() {
		Collection<Edge> mst = MST.prims(g6(),1);
		assertEquals(3, mst.size());
		int weight = 0;
		for (Edge e : mst) {
			weight += e.getWeight();
		}
		assertEquals(3, weight);
	}
	

	@Test(timeout = 500)

	public void ds1() {
		DisjointSets<Integer> ds = new DisjointSets<>(items(1, 2, 3, 4, 5, 6, 7));
		assertFalse(ds.sameSet(1, 2));
		ds.merge(1, 2);
		assertTrue(ds.sameSet(1, 2));
	}
	
	@Test(timeout = 500)

	public void ds2() {
		DisjointSets<Integer> ds = new DisjointSets<>(items(1, 2, 3, 4, 5, 6, 7));
		ds.merge(1, 2);
		ds.merge(3, 4);
		ds.merge(5, 6);
		ds.merge(5, 7);
		assertTrue(ds.sameSet(6, 7));
		assertFalse(ds.sameSet(1, 3));
		assertFalse(ds.sameSet(1, 7));
		ds.merge(1, 4);
		ds.merge(1, 7);
		assertTrue(ds.sameSet(1, 7));
		assertTrue(ds.sameSet(3, 6));
	}
	
	// checks path compression
	@Test(timeout = 1000)

	public void ds3() {
		int max = 100000;
		Set<Integer> items = new HashSet<>();
		for (int i = 0; i < max; i++) {
			items.add(i);
		}
		
		DisjointSets<Integer> ds = new DisjointSets<>(items);
		for (int incr = 2; incr < max; incr *= 2) {
			System.out.println(incr);
			for (int i = incr; i < max; i += incr) {
				//System.out.println(i +" "+ incr/2);
				ds.merge(i - (incr / 2), i);
			}
		}
		System.out.println("finally made it");
		ds.sameSet(0, max - 1);
		long start = System.currentTimeMillis();
		start = System.currentTimeMillis();
		// should have compressed path, should be almost instant to return the answer
		ds.sameSet(0, max - 1);
		long t = System.currentTimeMillis() - start;
		assertTrue(t < 10);
	}
	
	@Test(timeout = 350)

	public void ds4() {
		int max = 100;
		Set<Integer> items = new HashSet<>();
		for (int i = 0; i < max; i++) {
			items.add(i);
		}
		
		Random r = new Random(1332);
		DisjointSets<Integer> ds = new DisjointSets<>(items);
		for (int i = 0; i < max; i++) {
			ds.merge(r.nextInt(max), r.nextInt(max));
			//System.out.println("hit"+i);
		}
		
		// these are not random, the random object is seeded.
		assertTrue(ds.sameSet(1, 2));
		assertTrue(ds.sameSet(1, 3));
		assertTrue(ds.sameSet(1, 4));
		assertFalse(ds.sameSet(1, 5));
		assertTrue(ds.sameSet(2, 3));
		assertTrue(ds.sameSet(2, 4));
		assertFalse(ds.sameSet(2, 5));
		assertTrue(ds.sameSet(3, 4));
		assertFalse(ds.sameSet(3, 5));
		assertFalse(ds.sameSet(4, 5));
	}
	
	/*
	 * Methods for testing
	 */
	
	// graph 1
	private Graph g1() {
		return new Graph("5 1 2 2 1 4 3 1 3 3 2 4 2 4 3 2");
		
		// (1, 2   2) (1, 4   3) (1, 3   3) (2, 4    2) (4, 3   2)
	}
	
	// graph 1 answer
	private Collection<Edge> g1a() {
		return edges("3 1 2 2 2 4 2 4 3 2");
	}
	
	// graph 2
	private Graph g2() {
		return new Graph("9 1 2 1 1 3 4 2 3 5 2 4 10 3 6 10 2 6 6 4 6 1 4 5 2 5 6 3");
	}
	
	// graph 2 answer
	private Collection<Edge> g2a() {
		return edges("5 1 2 1 4 6 1 4 5 2 1 3 4 2 6 6");
	}
	//prim 2 answer
	private Collection<Edge> g2aa() {
		return edges("5 1 2 1 1 3 4 2 6 6 2 4 10 4 5 2");
	}
	
	
	// graph 3
	private Graph g3() {
		return new Graph("15 2 3 2 2 4 2 2 5 2 2 6 2 3 4 3 3 5 3 3 6 3 4 5 4 4 6 4 5 6 5 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1");
	}
	
	// graph 3 answer
	private Collection<Edge> g3a() {
		return edges("5 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1");
	}
	
	// graph 4
	private Graph g4() {
		return new Graph("8 1 4 100 1 5 1 1 6 3 5 2 2 2 6 2 2 7 1 6 3 2 3 7 3");
	}
	
	// graph 4 answer
	private Collection<Edge> g4a() {
		return edges("6 1 4 100 1 5 1 2 7 1 5 2 2 2 6 2 6 3 2");
	}
	
	// graph 5
	private Graph g5() {
		return new Graph("2 1 2 1 3 4 1");
	}
	
	// graph 5 answer
	private Collection<Edge> g5a() {
		return null;
	}
	
	// graph 6 (multiple valid answers) 
	private Graph g6() {
		return new Graph("6 1 2 1 1 3 1 1 4 1 2 3 1 2 4 1 3 4 1");
	}
	
	private Collection<Edge> edges(String s) {
		Scanner scan = new Scanner(s);
		Collection<Edge> edges = new HashSet<>();
		int num = scan.nextInt();
		for (int i = 0; i < num; i++) {
			edges.add(new Edge(new Vertex(scan.nextInt()), new Vertex(scan.nextInt()), scan.nextInt()));
		}
		scan.close();
		return edges;
	}
	
	private Collection<Edge> edges(Collection<Edge> edges) {
		return edges == null ? null : new HashSet<>(edges);
	}
	
	@SuppressWarnings("unchecked")
	private <T> Set<T> items(T ... items) {
		Set<T> ret = new HashSet<T>();
		for (T item : items) {
			ret.add(item);
		}
		return ret; 
		
	}
}
